package 力扣;

/**
 示例 1:
 输入: [3,2,3,null,3,null,1]
 3
 / \
 2   3
 \   \
 3   1

 输出: 7
 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
 示例 2:
 输入: [3,4,5,1,3,null,1]

       3
 / \
 4   5
 / \   \
 1   3   1

 输出: 9
 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
 * 示例 1:
 * 输入: [3,2,3,null,3,null,1]
 * 3
 * / \
 * 2   3
 * \   \
 * 3   1
 * <p>
 * 输出: 7
 * 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
 * 示例 2:
 * 输入: [3,4,5,1,3,null,1]
 * <p>
 *       3
 * / \
 * 4   5
 * / \   \
 * 1   3   1
 * <p>
 * 输出: 9
 * 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
 */

public class _337打家劫舍_III {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    int val;
    TreeNode left;
    TreeNode right;



    // 递归，由于只能间隔偷，所以需要比较子节点的 left 和 right 和 当前值 + 子子节点的left + 子子节点的 right
    public int rob(TreeNode root) {

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (root.left != null) {
            val += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            val += rob(root.right.left) + rob(root.right.right);
        }

        int val2 = rob(root.left)+rob(root.right);
        return  Math.max(val,val2);
    }
}